import math
import random


def assign_cluster(x, centroids):

    min_distance = float('inf')
    closest_idx = 0

    for i, centroid in enumerate(centroids):
        # 计算欧几里得距离
        distance = 0
        for j in range(len(x)):
            distance += (x[j] - centroid[j]) ** 2
        distance = math.sqrt(distance)

        if distance < min_distance:
            min_distance = distance
            closest_idx = i

    return closest_idx


def Kmeans(data, k, epsilon=1e-4, max_iterations=100):

    # 随机初始化质心
    centroids = random.sample(data, k)

    for iteration in range(max_iterations):
        # 分配每个点到最近的质心
        assignments = []
        for point in data:
            cluster_idx = assign_cluster(point, centroids)
            assignments.append(cluster_idx)

        # 更新质心
        new_centroids = []
        for i in range(k):
            # 找到属于当前簇的所有点
            cluster_points = []
            for j, point in enumerate(data):
                if assignments[j] == i:
                    cluster_points.append(point)

            # 计算新质心
            if cluster_points:
                new_centroid = []
                for dim in range(len(data[0])):
                    dim_sum = sum(point[dim] for point in cluster_points)
                    new_centroid.append(dim_sum / len(cluster_points))
                new_centroids.append(new_centroid)
            else:
                # 如果簇为空，保留原质心
                new_centroids.append(centroids[i])

        # 检查收敛
        total_movement = 0
        for old, new in zip(centroids, new_centroids):
            movement = 0
            for d1, d2 in zip(old, new):
                movement += (d1 - d2) ** 2
            total_movement += math.sqrt(movement)

        if total_movement < epsilon:
            break

        centroids = new_centroids

    return centroids, assignments